Graph Transformation, Specifications, and Nets by Reiko Heckel & Gabriele Taentzer

Author:Reiko Heckel & Gabriele Taentzer
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

Keywords

Graph transformationSoftware systemStatic analysis

1 Introduction

Graph transformation is a rule-based framework, suitable for modelling both static and dynamic aspects of complex systems in an intuitive yet formal manner [8, 24]. The main idea is to use graphs to specify the states of a system, describing existing entities and their relations at each time of execution, and to model the transitions between such states as graph rewriting rules, also called productions. These rules describe precisely how the states can be modified. Besides having an intuitive and visual representation, graph transformation has a solid formal background, which enables several analysis techniques.

There are several approaches to describe Graph Transformation (GT) [24], differing on the kinds of graphs that are used and how rules and their application are defined. In some approaches, these notions are defined using set theory. The algebraic approach to graph transformation [8] uses notions of category theory to describe graph transformation rules and rule application. Category theory provides a language to describe and reason about complex situations at a high level of abstraction. An advantage of this approach is that great part of the rich algebraic GT theory is applicable not only to a particular kind of graph, but also to several different structures such as labelled graphs, typed graphs, attributed graphs [8] and even transformation rules themselves [16]. This is possible since most of the theory is developed at the categorial level, as high-level replacement systems [11] or -adhesive categories [10]. The main idea is that theory is developed at a very abstract level assuming that the concrete category to which the theory should hold has particular properties. Then, by showing that specific graph categories have these properties, the theory immediately applies to them.

Although most of the algebraic GT theory is done at this abstract level, existing GT tools (AGG [26], Groove [22], among others), are implemented at a rather concrete level: each tool supports only a fixed set of concrete graph models, operations and analysis techniques. Furthermore, their implementation is very far from the formal definitions, hindering arguments about correctness and the construction of extensions to deal with novel approaches.

This led to the creation of the Verigraph System [7], which is open source1 and implemented in Haskell. It has a current focus on static analysis techniques and the following design goals: G1. Quick prototyping and experimentation of novel theory

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.